Concurrent and parallel algorithms are different. However, in the case of dictionaries, both kinds of algorithms share many\udcommon points. We present a unified approach emphasizing these points. It is based on a careful analysis of the sequential\udalgorithm, extracting from it the more basic facts, encapsulated later on as local rules. We apply the method to the\udinsertion algorithms in AVL trees. All the concurrent and parallel insertion algorithms have two main phases. A\udpercolation phase, moving the keys to be inserted down, and a rebalancing phase. Finally, some other algorithms and\udbalanced structures are discussed.
展开▼
